
let tree = {
    val: 1,
    left: {
        val: 2,
        left: {
            val: 4,
            left: null,
            right: null
        },
        right: {
            val: 5,
            left: null,
            right: null
        }
    },
    right: {
        val: 3,
        left: {
            val: 6,
            left: null,
            right: null
        },
        right: {
            val: 7,
            left: null,
            right: null
        }
    }
}







function morrisInorderTraversal(root) {
    let ans = [];


    while (root) {
        
        // 判断左子树是否存在
        if (root.left) {

            let mostRight = root.left;


            //左子树存在，则找到左子树最右节点。
            while (mostRight.right != root) {
                // 右节点在则走向右节点，否则走向左节点
                if (mostRight.right) mostRight = mostRight.right
                else {
                    if (mostRight.left) mostRight = mostRight.left
                    else break;
                }
            }

            // 判断mostRight节点的右子节点是否为空，若空则将mostRight的右子节点指向cur节点（这里就是root节点）。同时cur节点左移
            if (mostRight.right == null) {
                mostRight.right = root;
                root = root.left;
            }

            // 如果右子节点指向cur节点，则让右子节点为空，同时cur向右移
            if (mostRight.right == root) {
                ans.push(root.val)
                mostRight.right = null;
                root = root.right;
            }
        } else {
            // 如果没有左子树，说明当前为最左节点，故将结果压入栈，开始向左走。
            ans.push(root.val)
            root = root.right
        }

    }
    return ans;
}


console.log(morrisInorderTraversal(tree))